package gold.digger;

import gold.utils.InputUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC321 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
     * @param 此题目参考了别人代码
     * 不是因为复杂，而是因为经典
     * 未来需要再次复习此道题目
     * hard 难度考察的就是综合竞技能力
     * 例如这道题，就是三个复合函数组合而成
     * @return:
     */
    class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            int[] maxResult = null;
            for (int i = 0; i <= k; i++) {
                if (i <= nums1.length && k - i <= nums2.length) {
                    List<Integer> kLargestNumber1 = getKLargestNumber(nums1, i);
                    List<Integer> kLargestNumber2 = getKLargestNumber(nums2, k - i);

                    int[] mergeResult = merge(kLargestNumber1, kLargestNumber2);
                    if (isBigger(mergeResult, maxResult)) maxResult = mergeResult;
                }
            }

            return maxResult;
        }

        //获取长度为k的最大子序列
        public List<Integer> getKLargestNumber(int[] nums, int k) {
            List<Integer> pickList = new ArrayList<>();
            int remain = nums.length - k;
            for (int num : nums) {
                while (remain > 0 && pickList.size() > 0 && pickList.get(pickList.size() - 1) < num) {
                    pickList.remove(pickList.size() - 1);
                    --remain;
                }

                pickList.add(num);
            }

            return pickList.subList(0, k);
        }

        //合并两个有序子序列， 成为一个最大值
        public int[] merge(List<Integer> l1, List<Integer> l2) {
            int[] res = new int[l1.size() + l2.size()];

            //注意，被注释掉的又逻辑错误，应该使用剩余部分字典序判断，而不是简单的当前元素判断
//            int idx = 0, idx1 = 0, idx2 = 0;
//            while (idx1 < l1.size() && idx2 < l2.size()) {
//                if (l1.get(idx1) > l2.get(idx2)) {
//                    res[idx++] = l1.get(idx1++);
//                } else {
//                    res[idx++] = l2.get(idx2++);
//                }
//            }
//
//            while (idx1 < l1.size()) {
//                res[idx++] = l1.get(idx1++);
//            }
//
//            while (idx2 < l2.size()) {
//                res[idx++] = l2.get(idx2++);
//            }

            int idx1 = 0, idx2 = 0, idx = 0;
            StringBuilder sb1 = new StringBuilder();
            StringBuilder sb2 = new StringBuilder();
            for (int i = idx1; i < l1.size(); i++) sb1.append(l1.get(i));
            for (int i = idx2; i < l2.size(); i++) sb2.append(l2.get(i));
            String a = sb1.toString();
            String b = sb2.toString();
            while (idx1 < l1.size() || idx2 < l2.size()) {
                if (idx1 >= l1.size()) res[idx++] = l2.get(idx2++);
                else if (idx2 >= l2.size()) res[idx++] = l1.get(idx1++);
                else if (a.substring(idx1, l1.size()).compareTo(b.substring(idx2, l2.size())) >= 0) {
                    res[idx++] = l1.get(idx1++);
                } else {
                    res[idx++] = l2.get(idx2++);
                }
            }

            return res;
        }

        //前面的数是否大于后面的数
        public boolean isBigger(int[] candidate, int[] lastResult) {
            if (null == lastResult || lastResult.length == 0) return true;
            for (int i = 0; i < candidate.length; i++) {
                if (candidate[i] > lastResult[i]) return true;
                else if (candidate[i] < lastResult[i]) return false;
            }
            return false;
        }
    }

    public void run() {
        Solution solution = new Solution();
//        nums1 = [3, 4, 6, 5]
//        nums2 = [9, 1, 2, 5, 8, 3]

        final int[] ints1 = InputUtil.toIntegerArray("[6, 7]");
        final int[] ints2 = InputUtil.toIntegerArray("[6, 0, 4]");
        System.out.println(Arrays.toString(solution.maxNumber(ints1, ints2, 5)));
    }

    public static void main(String[] args) throws Exception {
        LC321 an = new LC321();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
